package com.wtgroup.demo.leetcode.q005_最长回文子串;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;

/**
 * 暴力递归到 DP
 *
 * @author nisus
 * @version 0.1
 * @since 2023/5/17 13:19
 */
public class D_Force2DP {

    public static void main(String[] args) {
        Judger.of(() -> {
            String sss = RandomUtil.randomString(RandomUtil.randomInt(0, 20));
            // String sss = "m2b9yy7z0h4u5";
            // String sss = "yy";

            String refer = new S_CenterExpand().longestPalindrome(sss);
            // String res = new D1().longestPalindrome(sss);
            String res = new D2().longestPalindrome(sss);

            // boolean r = refer.equals(res);
            boolean r = refer.length() == res.length();
            if (r == false) {
                System.out.println(sss);
                System.out.println(refer);
                System.out.println(res);
            }
            return r;
        }).setIterCount(1000).start().print();
    }

    static class D1 {
        public String longestPalindrome(String s) {
            if (s == null || s.length() < 2) {
                return s;
            }

            char[] chars = s.toCharArray();
            // [begin, len]
            int[] res = func(chars, 0, chars.length - 1);

            return s.substring(res[0], res[0] + res[1]);
        }

        private int[] func(char[] chars, int left, int right) {
            if (left > right) {
                return new int[]{-1, 0};
            }
            if (left == right) {
                return new int[]{left, 1};
            }

            int[] ans = new int[]{-1, 0};

            int[] res1 = func(chars, left + 1, right - 1);
            if (res1[0] == -1 || (res1[0] == left + 1 && res1[1] == right - left - 1)) {
                // 左右边界被包含了, 进一步看
                res1 = chars[left] == chars[right] ? new int[]{left, res1[1] + 2} : res1;
            }
            if (res1[1] > ans[1]) {
                ans = res1;
            }

            int[] res2 = func(chars, left + 1, right);
            if (res2[1] > ans[1]) {
                ans = res2;
            }

            int[] res3 = func(chars, left, right - 1);
            if (res3[1] > ans[1]) {
                ans = res3;
            }

            return ans;
        }

    }

    // fail!!
    static class D2 {

        class Info {
            int begin;
            int len;

            public Info(int begin, int len) {
                this.begin = begin;
                this.len = len;
            }
        }

        public String longestPalindrome(String s) {
            if (s == null || s.length() < 2) {
                return s;
            }

            char[] chars = s.toCharArray();
            int N = chars.length;
            Info[][] dp = new Info[N][N];
            for (int left = N - 1; left >= 0; left--) {
                for (int right = 0; right < N; right++) {
                    // if (left > right) {
                    dp[left][right] = new Info(-1, 0);
                    // continue;
                    // }
                    if (left == right) {
                        dp[left][right] = new Info(left, 1);
                        continue;
                    }

                    Info ans = new Info(-1, 0);

                    if (left + 1 < N && right - 1 >= 0) {
                        // int[] res1 = func(chars, left + 1, right - 1);
                        Info res1 = dp[left + 1][right - 1];
                        if (res1.begin == -1 || (res1.begin == left + 1 && res1.len == right - left - 1)) {
                            // 左右边界被包含了, 进一步看
                            res1 = chars[left] == chars[right] ? new Info(left, res1.len + 2) : res1;
                        }
                        if (res1.len > ans.len) {
                            ans = res1;
                        }
                    }

                    if (left + 1 < N) {
                        Info res2 = dp[left + 1][right];
                        if (res2.len > ans.len) {
                            ans = res2;
                        }
                    }

                    if (right - 1 >= 0) {
                        Info res3 = dp[left][right - 1];
                        if (res3.len > ans.len) {
                            ans = res3;
                        }
                    }

                    dp[left][right] = ans;
                }
            }


            // [begin, len]
            Info res = dp[0][chars.length - 1];

            return s.substring(res.begin, res.begin + res.len);
        }

        private int[] func(char[] chars, int left, int right) {
            if (left > right) {
                return new int[]{-1, 0};
            }
            if (left == right) {
                return new int[]{left, 1};
            }

            int[] ans = new int[]{-1, 0};

            int[] res1 = func(chars, left + 1, right - 1);
            if (res1[0] == -1 || (res1[0] == left + 1 && res1[1] == right - left - 1)) {
                // 左右边界被包含了, 进一步看
                res1 = chars[left] == chars[right] ? new int[]{left, res1[1] + 2} : res1;
            }
            if (res1[1] > ans[1]) {
                ans = res1;
            }

            int[] res2 = func(chars, left + 1, right);
            if (res2[1] > ans[1]) {
                ans = res2;
            }

            int[] res3 = func(chars, left, right - 1);
            if (res3[1] > ans[1]) {
                ans = res3;
            }

            return ans;
        }

    }

}
